package leetcode_数组.matrix;

import java.util.ArrayList;
import java.util.List;

/**
 * 螺旋矩阵
 * 算法：模拟
 *
 * @author origin
 */
public class _54 {
    public static void main(String[] args) {
        int[][] matrix = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};
        System.out.println(spiralOrder(matrix));
    }

    public List<Integer> spiralOrder_upgrade(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length, size = m * n;
        List<Integer> ans = new ArrayList<>(size);
        if (size == 0) return ans;
        int l = 0, r = n - 1, u = 0, d = m - 1;
        while (ans.size() < size) {
            for (int i = l; i <= r; i++) ans.add(matrix[u][i]);
            if (++u > d) break;
            for (int i = u; i <= d; i++) ans.add(matrix[i][r]);
            if (l > --r) break;
            for (int i = r; i >= l; i--) ans.add(matrix[d][i]);
            if (u > --d) break;
            for (int i = d; i >= u; i--) ans.add(matrix[i][l]);
            if (++l > r) break;
        }
        return ans;
    }

    public static List<Integer> spiralOrder(int[][] matrix) {
        ArrayList<Integer> ans = new ArrayList<>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return ans;
        }
        int m = matrix.length, n = matrix[0].length;
        int[][] direction = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        boolean[][] isAdd = new boolean[m][n];
        int flag = 0, i = 0, j = 0;
        while (ans.size() < m * n) {
            ans.add(matrix[i][j]);
            isAdd[i][j] = true;
            int nextI = i + direction[flag][0], nextJ = j + direction[flag][1];
            if (nextI < 0 || nextI >= m || nextJ < 0 || nextJ >= n || isAdd[nextI][nextJ]) {
                flag = (flag + 1) % direction.length;
            }
            i = i + direction[flag][0];
            j = j + direction[flag][1];
        }
        return ans;
    }

}
